public class Test1 {
    //leetcode 647 回文子串
    public int countSubstrings(String s) {
        //为什么这道题目可以选择动态规划来解决
        //当判断i，j之间的字符串是否为回文串的时候，如果i，j位置的字符相等，那么如果i+1，j-1之间的字串也是
        //回文串的话，那么i，j之间的子串就是回文串，也就是说，这道题目可以根据前面的某一个状态推导出当前的状态
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int ret = 0;
        for (int i =  n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    //当s.charAt(i) == s.charAt(j)有三种情况
                    //1.i==j，也就是一个字符的情况，根据题目一个字符也是回文子串
                    //2.i+1 == j,这时候i+1 > j-1，不符合状态转移方程，但是这种情况也属于回文子串，所以需要做出判断
                    //i + 1 < j，dp[i][j] = dp[i+1][j-1]
                    dp[i][j] = (i + 1 < j) ? dp[i+1][j-1] : true;
                    if (dp[i][j]) ret++;
                }
            }
        }
        return ret;
    }
}
